package com.huawei.M01.iterator.A24;

import java.util.HashMap;
import java.util.Map;

/**
 * 爬楼梯
 *
 * @author zhiwu
 */
public class ClimbStatus {

//    public int climbStairs(int n) {
//        Map<Integer, Integer> cache = new HashMap<>(n + 1);
//        cache.put(1, 1);
//        cache.put(2, 2);
//        dfs(n, cache);
//
//        return cache.get(n);
//    }
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
       int[] dp = new int[n + 1];
       dp[1] = 1;
       dp[2] = 2;
       for (int i = 3; i <= n; i++) {
           dp[i] = dp[i  - 1] + dp[i - 2];
       }
       return dp[n];
    }

//    private int dfs(int n, Map<Integer, Integer> cache) {
//        if (!cache.containsKey(n)) {
//            cache.put(n, dfs(n - 1, cache) + dfs(n - 2, cache));
//        }
//        return cache.get(n);
//    }


    public static void main(String[] args) {
        System.out.println(new ClimbStatus().climbStairs(1));
    }
}
